Facsimile systems are used for the electrical transmission of documents over long distances. The image of a document is broken up into a series of electrical signals which are transmitted to and received at a distant location. The signals are processed to reform the image of the original document.
Typically, the original document is scanned line by line. Each scan line covers a strip of the document and is a series of digital signals, each signal representing the state of a particular area on the strip. Typically, a "0" signal means that the corresponding area is "white" or unmarked. A "1" signal means that the area is marked, or "black," with part of a character or letter on the document, for example. Each scan line then has a sequence of "1"s and "0"s indicative of the image information on the strip.
Heretofore, this information was transmitted in this form, with each binary digital signal corresponding to a particular area on the document. More recently, efforts have been made to compress the amount of information sent to save transmission times and lower costs. One approach has been to code the digital information on each scan line. This technique is based upon the correlation of information in the horizontal direction, i.e., in the direction along the scan line. Each scan line consists of an alternating sequence of black and white color units, each color unit being, in turn, a sequence of binary digital signals all representing the same color. Each color unit is either all "1"s or all "0"s. For a discussion in greater detail of one-dimensional facsimile coding, also called run length coding, see the patent application, U.S. Ser. No. 524,817, entitled A Facsimile Device for Run Length Coding, filed of even date, by the applicants.
Another technique used in coding facsimile information is two-dimensional coding, in which the correlation of information in the vertical direction is used. Generally speaking, information of a reference line, which has already been processed, is used to code the information on a subsequent scan line, called the coding line. In two-dimensional coding, the run length coding discussed above is also used when the correlation of information in the vertical direction is not very high.
Both one-dimensional and two-dimensional coding techniques have been standardized. See, for example, "International Digital Facsimile Coding Standards," by Roy Hunter and A. Harry Robinson, Proceedings of the IEEE, Volume 68, number 7, July 1980, pages 854-867. As explained in that paper, two-dimensional coding uses "color change picture elements" which are the picture elements in each scan line, whose color is different from the color of the preceding picture element. In terms of color units, the change picture element is the first picture element of each color unit in a scan line. In two-dimensional coding the change picture elements in the coding line are coded with respect to the change picture elements in the reference line.
The present invention performs two-dimensional facsimile coding generally based upon the international standards above. However, by a novel method of performing the two-dimensional coding and a device to perform the coding, the present invention offers many advantages over the prior art. The exemplary invention offers a large improvement in speed over the prior art. This invention also permits the realization of the coding device in an integrated circuit using present day VLSI (very large scale integration) technology. The requirements in the prior art made such VLSI implementation unfeasible.